#include "typedef.h"
#include "mem.h"

/**
    Simple introduction by AI
    The allocation principle of First Fit is as follows:

    First Fit is a memory management algorithm used to allocate free partitions
    to processes that need them. The algorithm connects the free partition chains
    in ascending address order. When performing memory allocation, it sequentially
    searches from the head of the chain until a suitable free partition is found.
    When a suitable free partition is found, it allocates a block of memory
    space to the requester according to the size of the job.

    The First Fit algorithm tends to preferentially utilize the low-address
    portion of memory's free partitions, thus preserving large free areas in
    the high-address portion. This provides conditions for assigning large memory
    spaces to large jobs. However, as the low-address portion is constantly divided,
    many small fragments of free space are left behind, which are difficult to
    utilize and are referred to as "fragments".
 *
 */


enum __ff_block_status
{
    MASK=0xeaebecc0,
    BUSY=0xeaebecca,
    FREE=0xeaebecc7,
};

typedef struct ffBlock
{
    enum __ff_block_status magic;
    int block_size;
    struct ffBlock *prev;
    struct ffBlock *next;
} *ffBlock;

static ffBlock ff_head;

static boolean is_block_free(ffBlock b)
{
    return b->magic == FREE;
}

static boolean is_corrupted(ffBlock b)
{
    return (b->magic & 0xfffffff0) != MASK;
}

static void mark_as_free(ffBlock b)
{
    b->magic = FREE;
}

static void mark_as_busy(ffBlock b)
{
    b->magic = BUSY;
}

static boolean should_split(int bs, int rs)
{
    // 8byte as the minimal split threshold
    return bs - rs > sizeof(struct ffBlock);
}

static void* move_to_payload(ffBlock b)
{
    return CAST_AS(void*, (void*)b+sizeof(struct ffBlock));
}

static ffBlock move_to_control(void *ptr)
{
    return CAST_AS(ffBlock, ptr - sizeof(struct ffBlock));
}

static void do_split(ffBlock b, int new_size)
{
    /*
    before split:
    +-------------------------+-----------+
    |  b                      | block_next|
    +-------------------------+-----------+
    after split:
    +-----+-------------------+-----------+
    |  b  | new_block         | block_next|
    +-----+-------------------+-----------+
    */
    ffBlock new_block = CAST_AS(ffBlock, (void*)b + new_size);
    ffBlock block_next = b->next;
    b->next = new_block;
    if (block_next)
    {
        block_next->prev = new_block;
    }
    new_block->prev = b;
    new_block->next = block_next;
    new_block->block_size = b->block_size - new_size;
    b->block_size = new_size;
}

static void do_merge(ffBlock ba, ffBlock bb)
{
    /*
    before merge:
    +--------------+-----------+-----------+
    |  ba          | bb        | bb_next   |
    +--------------+-----------+-----------+
    after merge:
    +--------------------------+-----------+
    |  ba                      | bb_next   |
    +--------------------------+-----------+
    */
    ffBlock bb_next = bb->next;
    ba->block_size += bb->block_size;
    ba->next = bb_next;
    bb_next->prev = ba;
}


void init_ff_alloc(address start, int size)
{
    ff_head = start;
    int total_size = size;
    total_size = word_align_down(total_size);
    int free_size = total_size - sizeof(struct ffBlock);
    ff_head->block_size = total_size;
    ff_head->prev = ff_head->next = NULL;
    do_split(ff_head, free_size);
    ffBlock guard = ff_head->next;
    mark_as_busy(guard);
    mark_as_free(ff_head);
}

void *ff_alloc(int size)
{
    ffBlock t = NULL;
    ffBlock b = ff_head;
    size = word_align_up(size) + sizeof(struct ffBlock);
    for (; b; b = b->next)
    {
        if (b->block_size < size)
        {
            continue;
        }
        if (!is_block_free(b))
        {
            continue;
        }
        t = b;
        if (should_split(t->block_size, size))
        {
            do_split(t, size);
            mark_as_free(t->next);
        }
        break;
    }
    if (!t)
    {
        return NULL;
    }
    mark_as_busy(t);
    return move_to_payload(t);
}

void ff_free(void *ptr)
{
    ffBlock b = move_to_control(ptr);
    if (is_corrupted(b))
    {
        // corrupted, do recover
    }
    ffBlock prev = b->prev;
    ffBlock next = b->next;
    if (prev && is_block_free(prev))
    {
        do_merge(prev, b);
        b = prev;
    }
    if (next && is_block_free(next))
    {
        do_merge(b, next);
    }
    mark_as_free(b);
}